package com.steve.combat.algorithm.douyin;

/**
 * @Author: STEVE
 * @Description: 经典背包问题 - 动态规划
 * @since: 2025-04-20
 */
public class Knapsack {

    /**
     * 给定一个背包，容量为 W（最大承重），以及 N 个物品，每个物品有：
     * weight[i]：重量
     * value[i]：价值
     * 目标：选择一些物品装入背包，使得 总重量 ≤ W，且 总价值最大。
     * 限制：每个物品 要么选，要么不选（不能拆分，故称 0-1 背包）
     *
     * 定义 dp[i][j]：前 i 个物品，背包容量为 j 时的最大价值。
     * 状态转移方程：
     * 不选第 i 个物品：dp[i][j] = dp[i-1][j]
     * 选第 i 个物品（需 j ≥ weight[i]）：dp[i][j] = dp[i-1][j-weight[i]] + value[i]
     * 最终取较大值：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
     */
    public static int knapsack(int W, int[] weight, int[] value, int N) {
        int[][] dp = new int[N + 1][W + 1];
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= W; j++) {
                if(weight[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i -1][j],    // 不选第i个物品
                            dp[i - 1][j - weight[i - 1]] + value[i - 1]);   // 选第i个物品
                } else {
                    dp[i][j] = dp[i - 1][j];    // 当前物品超重，不能选
                }
            }
        }
        return dp[N][W];
    }

    public static void main(String[] args) {
        int W = 50; // 背包容量
        int[] weight = {10, 20, 30}; // 物品重量
        int[] value = {60, 100, 120}; // 物品价值
        int N = weight.length; // 物品数量

        System.out.println(knapsack(W, weight, value, N)); // 输出 220（选物品 2 和 3）
    }

}
